package Leetcode.Dichotomy;

/**
 * @Author: kirito
 * @Date: 2024/4/11 14:53
 * @Description:
 * 寻找峰值 II
 * 已解答
 * 中等
 * 相关标签
 * 相关企业
 * 提示
 * 一个 2D 网格中的 峰值 是指那些 严格大于 其相邻格子(上、下、左、右)的元素。
 *
 * 给你一个 从 0 开始编号 的 m x n 矩阵 mat ，其中任意两个相邻格子的值都 不相同 。找出 任意一个 峰值 mat[i][j] 并 返回其位置 [i,j] 。
 *
 * 你可以假设整个矩阵周边环绕着一圈值为 -1 的格子。
 *
 * 要求必须写出时间复杂度为 O(m log(n)) 或 O(n log(m)) 的算法
 *
 *
 * 示例 1:
 *
 *
 * 输入: mat = [[1,4],[3,2]]
 * 输出: [0,1]
 * 解释: 3 和 4 都是峰值，所以[1,0]和[0,1]都是可接受的答案。
 * 示例 2:
 *
 *
 * 输入: mat = [[10,20,15],[21,30,14],[7,16,32]]
 * 输出: [1,1]
 * 解释: 30 和 32 都是峰值，所以[1,1]和[2,2]都是可接受的答案。
 *
 * 提示：
 *
 * m == mat.length
 * n == mat[i].length
 * 1 <= m, n <= 500
 * 1 <= mat[i][j] <= 105
 * 任意两个相邻元素均不相等
 */

public class findPeakGrid {
    public int[] findPeakGrid(int[][] mat) {
        int m = mat.length, n = mat[0].length;
        // 获取矩阵的行数m和列数n

        int low = 0, high = m - 1;
        // 设置二分搜索的行索引范围，low为起始行，high为结束行

        while (low <= high) {
            int mid = (low + high) / 2;
            // 计算中间行索引i

            int j = -1, maxElement = -1;
            // 初始化列索引j和最大元素值maxElement

            for (int k = 0; k < n; k++) {
                // 遍历中间行，找到最大元素及其列索引
                if (mat[mid][k] > maxElement) {
                    j = k;
                    maxElement = mat[mid][k];
                }
            }

            if (mid - 1 >= 0 && mat[mid][j] < mat[mid - 1][j]) {
                // 如果当前行的最大元素小于上一行的对应元素，说明峰值在上边，调整搜索范围到上半部分
                high = mid - 1;
                continue;
            }
            if (mid + 1 < m && mat[mid][j] < mat[mid + 1][j]) {
                // 如果当前行的最大元素小于下一行的对应元素，说明峰值在下边，调整搜索范围到下半部分
                low = mid + 1;
                continue;
            }
            // 如果当前行的最大元素既不小于上一行的对应元素，也不小于下一行的对应元素，说明找到了峰值
            return new int[]{mid, j};
        }

        return new int[0]; // 如果没有找到峰值，返回空数组，这在题目中是不可能的
    }

}
